package com.icbc.DataStructuresAndAlgorithms;

import org.junit.Test;

import java.util.Arrays;

/**
 * 排序算法
 */
public class SortList {
	static int count = 1;
	
	public static void main(String[] args) {
		
		int[] arr = {12 , 1 , 6 , 7 , 2 , 9 , 7 , 8 , 7 , 7 , 6 , 2 , 5 };
		//int[] arr = {4,6,8,5,9};
		/*System.out.println("************冒泡排序**************");
		SortList.SortMaoPao(arr);
		System.out.println(Arrays.toString(arr));*/
		/*System.out.println("************选择排序**************");
		SortList.sortXuanZe(arr);
		System.out.println(Arrays.toString(arr));*/
		/*System.out.println("************插入排序**************");
		SortList.sortXuanZe(arr);
		System.out.println(Arrays.toString(arr));*/
		/*System.out.println("************希尔交换排序**************");
		SortList.sortXiErJiaoHuan(arr);
		System.out.println(Arrays.toString(arr));*/
		/*System.out.println("************希尔插入排序**************");
		SortList.sortXiErChaRu(arr);
		System.out.println(Arrays.toString(arr));*/
		System.out.println("************快速排序**************");
		SortList.sortKuaiSu(arr,0,arr.length - 1);
		System.out.println(Arrays.toString(arr));
		System.out.println(count);
		/*System.out.println("************归并排序**************");
		int[] temp = new int[arr.length];
		SortList.sortMerge(arr,0,arr.length - 1,temp);
		System.out.println(Arrays.toString(arr));*/
		/*System.out.println("************基数排序**************");
		SortList.sortJiShu(arr);
		System.out.println(Arrays.toString(arr));*/
		/*System.out.println("************堆排序**************");
		//SortList.sortDui(arr);
		SortList.sortDui(arr);
		System.out.println(Arrays.toString(arr));*/
	}
	
	@Test
	public void test(){
		int[] arr = new int[80000000];
		for (int i = 0; i < arr.length; i++) {
			arr[i] = (int)(Math.random()*80000000);
		}
		//int[] temp = new int[arr.length];
		long s = System.currentTimeMillis();
		SortList.sortKuaiSu(arr,0,arr.length - 1);
		long e = System.currentTimeMillis();
		System.out.println(e-s);
		//System.out.println(Arrays.toString(arr));
	}
	
	//冒泡排序
	public static void SortMaoPao(int[] arr){
		int num; //num为中间缓存变量,用于相邻的两个数据交换时作为临时存储
		/*
		 * 开始循环,外层循环表示共需要对比几趟,应该是数据长度-1趟
		 * 在这里之所以进行逆向循环是在内层对比时每一趟都会比上一趟少一次对比
		 */
		for (int i = arr.length - 1; i > 0 ; i--) {
			/*
			 * 定义一个标识,初始化为true,用于对冒泡排序的优化,
			 * 当这一趟没有任何数据交换时就认为当前数据已经排好序了,就跳出循环
			 */
			boolean flag = true;
			/*
			 * 内层循环,从s = 0开始到s < i结束,这里之所以不是s <= i是因为,i时就已经是此数组最后的下标了
			 * 上面i = a.length - 1时,下标是从0开始的,所以i是数组最后的下标,而在下面的代码中使用到s + 1下标
			 * 所以这里让循环到s < i
			 */
			for(int s = 0 ; s < i ; s ++){
				//判相邻的两个元素,当前一个元素比后一个元素大时,进入if中将这两个元素的值进行交换
				if (arr[s] > arr[s + 1]){
					//当进了if就把flag标识改为false,表示这一趟比较有需要交换的数据,还没有排好序
					flag = false;
					//将前一个数据先赋给临时变量保存起来,然后将数据进行交换
					num = arr[s];
					arr[s] = arr[s + 1];
					arr[s + 1] = num;
				}
			}
			/*
			 * 当一趟结束后,查看标识是否为true,为true时表示此趟比较没有需要交换的数据,
			 * 已排好顺序,不再执行下一趟比较
			 */
			if (flag){
				break;
			}
		}
	}
	
	//选择排序
	public static void sortXuanZe(int[] arr){
		int num;//num为中间缓存变量,用于两个数据交换时作为临时存储
		/*
		 * 开始循环:外层循环为循环整个数组,且由于内部有比较所以外层循环可循环数组长度-1此即可
		 * 也可理解为共需要比较数组长度-1趟
		 */
		for (int i = 0 ; i < arr.length - 1 ; i++) {
			//定义一个变量用于记录较小值所在的下标,初始默认头一个值为最小值
			int index = i;
			/*
			 * 内层循环从i + 1开始,因为在上一层时可得的最小值不再进行比较
			 * 到arr.length结束,因为数组的最后一个数据也要比较
			 */
			for (int n = i + 1 ; n < arr.length ; n++) {
				/*
				 * 当当前的数据比被比较的数据大时,说明一开始假定的数据不是最小值
				 * 这时需要记录该最小值的下标,在下一次比较时则使用当前得到的最小值跟后面的比较
				 */
				if(arr[index] > arr[n]){
					//将当前最小值的下标赋给index,在下次比较时就是当前得到的最小值进行比较
					index = n;
				}
			}
			//当得到的最小值跟外层循环的的下标不一致时,将两个数据进行交换,否则什么也不做
			if (index != i){
				num = arr[i];
				arr[i] = arr[index];
				arr[index] = num;
			}
		}
	}
	
	//插入排序
	public static void sortChaRu(int[] arr){
		/*
		 * 插入排序思路:在插入排序中,依次从数组的第二个数据开始,拿此数据n跟
		 * 前面的数据依次从后往前进行比较,当此数据比前面的某个数据m小时,
		 * 表示该数据n应该放到m的前面,但注意在这里并不是说n的位置已经确定了
		 * 仅表示n在m之前,而m数据需要向后移动一位,使用一个标识(index)记录下
		 * 此处m原本的位置,并将标识向前移动进行index--操作,还是进行比较,
		 * 当n的值大于某个数据m1时,那么index指向的索引就是n值需要放置的位置
		 * 如果n值特别小,也不能让index无限--下去,当index为0时,n值就需要放在
		 * 数组的开头位置了
		 *
		 * 外层循环:表示第一个值为有序的,仅循环后面的数据,拿后面的数据
		 * 依次跟前面的数据进行比较,并放到合适的位置
		 */
		for (int i = 1; i < arr.length; i++) {
			//将需要进行排序的值取出
			int value = arr[i];
			//记录需要排序的值的索引位置
			int index = i;
			/*
			 * 内层循环:表示当退出此循环时index就是需要排序的值放置的位置
			 * index > 0表示防止索引越界且后面的条件一直不成立时
			 * 需要排序的值应放在数组的开头位置
			 * value < arr[index - 1] 表示需要排序的值n与n前面的值m依次进行比较
			 * 当n小于m时表示n应在m之前,那么m就需要向后移动
			 */
			while (index > 0 && value < arr[index - 1]){
				//表示将m值向后移动,这里是直接覆盖了原来的值,但在上面已经将值取出并记录
				arr[index] = arr[index - 1];
				//将索引向前移动指向下一个需要比较的索引位置
				/*
				 * 在这里的思路之所以是从后往前的方式遍历比较,其主要原因是需要将数据进行后移
				 * 如果是从前往后进行比较的话,当得到合适的位置时,在插入数据的时候,那些需要进行
				 * 后移数据的操作又是一个比较繁琐的事情
				 */
				index--;
			}
			/*
			 * 当循环结束时,index的值只有当index为0或者value >= arr[index - 1]时,
			 * 前者表示value应放在数组的开头,后者表示遇到了一个数值,这个数比需要排序的值小,
			 * 而需要排序的值应该放在此值的后面,而index刚好就是这个位置
			 */
			arr[index] = value;
		}
	}
	
	//希尔排序交换法,使用80000个数据进行排序,耗时14.6s左右
	//此方式算是对冒泡排序的优化,并不是对插入排序的优化,且此方式仅提升效率20%左右
	public static void sortXiErJiaoHuan(int[] arr){
		//首先将数组进行分组
		int num = arr.length / 2;
		//定义一个数组交换的中间变量存储数据
		int temp;
		/*
		 * 当num为1时是最后一次排序,但整型1除以2时,得到的还是整型且为0,
		 * 所以这里以num > 0为退出循环的条件
		 */
		while (num > 0) {
			//开始循环数组,但这里的循环次数有个问题
			/*
			 * 注意:例如长度为10的数组arr进行第一次分组时,分为5组,
			 * 而每个组的数组进行比较交换的话,又需要每个组都进行循环,但循环一次
			 * 是不行的,在这个对每个组交换类似与冒泡排序,需要将每个组再次进行两层循环
			 * 如:
			 * 	for (int i = 0 ; i < num ; i ++){
			 * 		for (int n = i ; n < arr.length - num ; n += num){
			 * 			for (int j = n ; j >= 0 ; j -= num) {
			 * 				if (arr[j] > arr[j + num]) {
			 * 					temp = arr[j];
			 * 					arr[j] = arr[j + num];
			 * 					arr[j + num] = temp;
			 * 				}
			 * 			}
			 * 		}
			 * 	}
			 * 当第一次分组排序完毕后,进行第二次分组,分为2组,这时问题就出现了,
			 * 共两组,每组五个数据,每个数据都需要与其他数据比较共需循环5-1次,正规的想法是循环两个组
			 * 在内层有一个循环,循环四次,在这个循环中还有一个循环,循环开每个数据,依次进行
			 * 比较,但中间的两层循环可以合并为for(int i = 0;i < num * (arr.length/num -1) ; i ++)
			 * num * (arr.length/num - 1) = num * arr.length/num - num = arr.length - num
			 * 中间的两个循环也就合成了for (int i = num; i < arr.length ; i ++)这个循环
			 * 里面的循环就是最开始思路里最里面的那个冒泡比较交换循环
			 */
			for (int i = num; i < arr.length ; i ++) {
				/*
				 * 内层循环表示将上面分好的组的每个数组进行循环开,在按照一定的规则顺序下进行比较排序
				 * 这里的规则是从头向后比较,每将后面的一个数值加入都跟前面的值进行比较并交换,
				 * 还有一种,是将从后向前比较,每将前面的一个数值加入都跟后面的值进行比较并交换
				 */
				for (int j = i - num ; j >= 0 ; j -= num) {
					if (arr[j] > arr[j + num]) {
						temp = arr[j];
						arr[j] = arr[j + num];
						arr[j + num] = temp;
					}
				}
			}
			//每次都对数组按照此方式进行分组,在上次分组的基础上再次分组
			num = num / 2;
		}
	}
	
	//希尔排序插入法,使用80000个数据进行排序,耗时30ms左右
	//此方式是对简单插入排序的优化,性能的提升比较明显
	public static void sortXiErChaRu(int[] arr){
		//先将数组进行分组为arr.length / 2个组
		int num = arr.length / 2;
		//定义两个中间的变量,用来记录需要排序的值与其索引值
		int value;
		int index;
		/*
		 * 当num为1时是最后一次排序,但整型1除以2时,得到的还是整型且为0,
		 * 所以这里以num > 0为退出循环的条件
		 */
		while (num > 0) {
			
			/*
			 * 与上面的交换排序类似,在这里同样有一个循环次数的问题,
			 * 按照正常的逻辑是先循环每个分组,在循环分组中的每个元素
			 * 如下方式:
			 * for (int i = 0; i < num ; i ++) {
			 * 		for(int n = i + num ; n < arr.length ; n += num) {
			 * 			value = arr[n];
			 * 			index = n;
			 * 			while (index > i && value < arr[index - num]) {
			 * 				arr[index] = arr[index - num];
			 * 				index -= num;
			 * 			}
			 * 			arr[index] = value;
			 * 		}
			 * 	}
			 * 但由于内循环的次数是分组元素的个数-1,也就是外层加内层的循环次数应该是
			 * num * (arr.length/num -1)次,那么可将两层循环进行整合为
			 * arr.length - num 次,也就是下面的编写方式,这种方式每个元素都会得到遍历
			 * 与上面的方式功能相同
			 */
			for (int i = num; i < arr.length ; i ++) {
				//将需要进行排序的元素进行记录值及其索引位置
				value = arr[i];
				index = i;
				/*
				 * 在这里进行插入排序,与插入排序类似,但这里仍有个问题,
				 * 由于i处于变化中,当分组后,我们怎么知道每个分组的第一个元素的索引呢,
				 * 也就是当某个分组后面的一个值是最小的,需要放在该分组的头位置,但由于上面的循环
				 * 是直接循环元素了,并没有循环分组,这里就需要思考怎么获取该分组的头索引了
				 * 当分为2组时,每个分组有5个元素,由于在分组时是按照num进行分组的,那么当移动标识index
				 * 指向的值 < num时,就表示此时index指向的位置就是此分组的头位置,那么判断头索引的条件
				 * 就是index < num 也就变成了下面当index >= num时就表示还未到分组的头,还可以继续向前移动
				 * 在这里也可以写成index > i % num,其中i % num的值就是该分组的头索引值,所以这里
				 * 不能让index = i % num 了,而上面的是因为数组是从0开始的,第num个元素刚好是
				 * 第二轮的开头元素索引
				 */
				while (index >= num && value < arr[index - num]) {
					//将该位置的元素值进行后移
					arr[index] = arr[index - num];
					//标识也向前移动
					index -= num;
				}
				/*
				 * 当跳出循环时刚好满足index < num 或者 value > arr[index - num]
				 * index < num表示index的位置在该分组的头位置
				 * value > arr[index - num]表示此值比value要小,而value刚好应该放在此值的后面
				 */
				arr[index] = value;
			}
			//每次都对数组按照此方式进行分组,在上次分组的基础上再次分组
			num = num / 2;
		}
	}
	
	//快速排序
	public static void sortKuaiSu(int[] arr,int left,int right){
		/*
		 * 获取数组中间值,作为标识,在此值的左边是小于此值的,
		 * 此值的右边是大于此值的,在这里之所以获取中间变量写成
		 * arr[(right + left) / 2];的方式是为了在递归时
		 * 同样可以获取分组后的中间量
		 */
		int pivot = arr[(right + left) / 2];
		//temp是用于数据交换的中间变量
		int temp;
		/*
		 * 这里之所以要用r接收right,是为了保持right不变
		 * 且也是为了递归时不受影响
		 */
		int r = right;
		int l = left;
		/*
		 * 开始循环,在这里循环的基本思路是:
		 * 从两边像中间开始寻找不符合左边小于中间的值,右边大于中间的值
		 * 在两边进行查找时使用一个变量进行记录也就是l记录左边,r来记录右边
		 * 没找到不符合条件的就将标识分别进行++与--的位移操作,在这个过程中
		 * l与r的值在不断的接近,当l >= r时表示整个数组已经遍历结束可以退出循环
		 */
		while (l < r){
			/*
			 * 遍历数组中间值的左边
			 * 在这里之所以不使用arr[l] <= pivot是因为在移动的过程中pivot
			 * 也可能被移动,这时就得记录与pivot相同的值,将它进行移动
			 * 或者遇到与pivot相同的值时也需要将此数据进行记录,并将它进行移动
			 */
			while (arr[l] < pivot){
				l++;
			}
			//遍历数组中间值的右边,与上面的原理相同
			while (arr[r] > pivot){
				r--;
			}
			/*
			 * 在里加此条件的意义在于在上面的操作过程中,无论是左遍历还是右遍历都
			 * 不知道遇到的pivot究竟是不是到了中间,而且这里也不能使用下标来判断,
			 * 因为在移动的过程中pivot也可能被移动,那么在这里就有个问题,万一左遍历
			 * 已经遍历到右边呢,得到的值l已经大于或者等于r了,这时是应该退出循环的,
			 * 但退出循环的条件在while的()中,这里并没有执行到那,所以需要添加以下
			 * 代码进行再次判断是否遍历结束
			 */
			if (l >= r){
				break;
			}
			
			/*
			 * 依照上面的逻辑,在上面的循环中要么找到了一个位于左边但大于标识pivot的值
			 * 和位于右边小于标识pivot的值,这时需要将这两个值进行交换即可
			 * 要么左边指向的就是pivot或者与pivot相同的值,而右边是一个小于pivot的值或者
			 * 与pivot相同的值但不是中间值,因为上面的if判断了l >= r的情况,所以l和r不可能
			 * 指向同一个值,在这时也将两个值进行互换.互换之后中间值pivot可能发生了改变,
			 * 但由于r与l的值未改变所以会继续遍历,在下次循环时l指向pivot会直接向下记录该值,
			 * 而r会继续走找到下一个小于pivot的值,将他们交换后会反过来,r指向pivot,让l来找大于
			 * pivot的值,找到后交换,如此循环下来,最终r与l都指向了pivot为止.
			 */
			if (arr[r] == arr[l]) {
				r--;
			}else{
				temp = arr[l];
				arr[l] = arr[r];
				arr[r] = temp;
			}
			//System.out.println(Arrays.toString(arr));
			/*
			 *注意:这里有一个大问题,如果r与l指向的都是与pivot相同的值,但又满足l < r,
			 * 也就是在数组中有一个或者多个值与pivot相同,这时将他们的值进行交换后再次遍历时
			 * 由于r与l的值并没有改变依然是与pivot相同的值,在上面的while查找时会直接跳过,
			 * 所以指向的还是交换后的那两个与pivot相同的值,这时整个
			 * 循环就陷入了死循环之中,所以在值交换后,我们要进行判断,当r或者l指向与pivot相
			 * 同的值时一定要将r或者l的指针向前移一位,避免死循环的发生
			 * 这里判断之所以arr[r] == arr[l]的情况,是当arr[r] == arr[l]时,其值一定为pivot
			 */
			/*if (arr[r] == arr[l]){
				r--;
			}*/
		}
		System.out.println(Arrays.toString(arr));
		/*
		 * 当循环完毕后表示上面得出的数组已经按照左边小右边大的方式排列好了,但这仅仅是完成了一次
		 * 还需要对pivot左边的数组进行上面的操作,因为是重复性的,所以使用递归对左边进行排列,
		 * 要使用递归首先得确认边界值,从哪里开始,到哪里结束从上面可知在进行左递归是应该从
		 * 0开始到pivot的前一个结束,因为上面时l >= r时退出循环,也就是left到l之前的一个数为
		 * 左递归区间,而r的前一个数到right是右递归的区间,要明白的是上面的判断:
		 * if (arr[r] == arr[l]){
		 * 		l++;
		 * }
		 * 虽然是为了防止死循环而写的,但当退出循环时,r与l都指向pivot的索引,这时直接将左分组的区间
		 * 定为left到l是不对的,l是指向pivot的,所以区间应该是left到l - 1,而r同样也是指向pivot的
		 * 所以右分组应该是r + 1到right,当然在这里r == l == pivot的索引,所以左分组区间left到r - 1
		 * 左分组区间l + 1到right也是对的,就需要将l++且r--,而且在这里必须有此操作,不然会无限递归
		 *
		 * 无限递归的原因:因为当执行递归时,如果先执行左递归,那么递归到最前面两个数时,此时的right应
		 * 该为1而l为0,此时开始递归,当上面的while循环结束时,如果错位进行交换,退出循环时r == l == 0,
		 * 因为r在进行--而小的值一定在向头移动,又因为pivot为中间值,当有两个数是pivot指向的一定是第一个数
		 * 这时arr[l] == pivot,而arr[r] > pivot,因此r--后跟l相同,跳出循环后left与r都为0不执行左递归
		 * 但right为1,l为0刚好满足右递归,但右递归还是头两个数,又会得到相同的结果,导致无限递归,而数组中若
		 * 有相同的值时,由于没有验证边界,也会不断的递归对相同的两个数进行交换.
		 *
		 * 出现这种现象的原因是:由于边界的不清晰,导致在递归时每次都会包含边界,当数量多时并不会影响,但当剩下
		 * 两个数据时,由于每次都包含边界,导致无法去掉一个值,进而一直判断这两个数据,且如果数据中有重复数据时
		 * 由于包含边界,也导致数据无法去除掉重复的数据,
		 */
		if (r == l){
			l++;
			r--;
		}
		if (left < r){
			sortKuaiSu(arr, left, r);
		}
		if (right > l){
			sortKuaiSu(arr, l, right);
		}
	}
	
	/**
	 * 功能 : 归并排序,合并的过程
	 * @param arr		需要排序的数组
	 * @param left		左分组的起始索引
	 * @param mid		分组的分割标识索引
	 * @param rightend	结束索引
	 * @param temp		中间储存数组
	 */
	public static void merge(int[] arr, int left, int mid, int rightend,int[] temp){
		//定义左分组的起始位置,用于遍历,mid是左分组的结束索引
		int l = left;
		//r为右分组的起始位置,rightend是右分组的结束索引
		int r = mid + 1;
		/*
		 * 此处的index是temp数组的索引,在将排序的数据放入temp数组时,需要有一个指针记录
		 * temp的数据位置,这里之所以将index = left是为了在下面将temp的数据复制到arr
		 * 数组时数据的位置保持一致,这里也可将index = 0,但下面进行复制时,temp数据就需
		 * 要每次从头取出
		 */
		int index = left;
		/*
		 * 开始循环,这里需要将两个有序分组的数据进行有序整合
		 * 思路 :
		 * 		将左分组的第一个数据与右分组的第一个数据进行比较,哪个数小就放到temp数组中
		 * 	将该分组的指针后移一位,再次进行比较,依次类推,直到某个分组的数据取完,但这里需要注意
		 * 	一个分组的数据取完时,另一个分组的数据并没有取完,这时需要判断是哪个分组还有数据
		 * 	将该分组的数据依次放入temp数组中即可
		 */
		while (true) {
			//判断左分组的数据大于右分组的数据时
			if (arr[l] > arr[r]){
				//将较小的数据放入temp数组中,将r指针后移
				temp[index++] = arr[r++];
			} else {
				//反之相同,将l指针后移
				temp[index++] = arr[l++];
			}
			/*
			 * 当r > rightend表示右分组的数据已经全部取出,那么就表示左分组还有数据未取出
			 * 在这里需要将左分组的数据依次取出放入temp数组中,放置完毕后两个分组的
			 * 数据合并就完成了,也就退出了循环
			 */
			if (r > rightend){
				while (l <= mid) {
					temp[index++] = arr[l++];
				}
				break;
			}
			/*
			 * 当l > mid表示左分组的数据已经全部取出,那么就表示右分组还有数据未取出
			 * 在这里需要将右分组的数据依次取出放入temp数组中,放置完毕后两个分组的
			 * 数据合并就完成了,也就退出了循环
			 */
			if (l > mid){
				while (r <= rightend) {
					temp[index++] = arr[r++];
				}
				break;
			}
		}
		/*
		 * 当数据合并后,此时的数据是存储在temp数组中,arr数组并没有变化,所以在这里需要
		 * 将temp中的数据复制到arr数组中,使arr数组变为有序的数组
		 * 这里注意上面的排序是分段排序,所以仅将本次合并的部分复制到arr数组中即可
		 * 那么排序的部分可知是left-rightend之间的部分,所以循环条件是left <= eightend
		 * 由于上面index = left,所以temp的有效数据也是存储在left-rightend区间之中
		 */
		while (left <= rightend) {
			arr[left] = temp[left];
			left++;
		}
	}
	
	/**
	 * 功能: 归并排序,分+合的过程
	 * 效率: 80000数据16ms,8000000在2.8秒左右,8千万数据在24秒左右
	 * @param arr	需要排序的数组
	 * @param left	从left开始对数组进行分割
	 * @param right	分割到right结束
	 * @param temp	中间临时数组
	 */
	public static void sortMerge(int[] arr, int left,int right,int[] temp){
		/*
		 * 此递归的思想:
		 * 		首先需要对数组进行分割,每次都是从中间进行分割,直到每组仅有一个元素为止,
		 * 	那么在这里分割的数据时从left到right之间的,那么什么时候代表此分组不可分割了呢
		 * 	就是left >= right时,代表该分组仅剩一个元素了,不能再分了,如果left < right时
		 * 	表示该分组还能在分,此时进入if中,计算出两个分组的中间界限索引,也就是
		 * 	(left + right) / 2,得到分割位置,得到分割位置时就已经知道左分组和右分组的界限了
		 * 	这时就可以继续对其进行分割,但由于分为左右两组,所以需要左右两组都进行分割,也就是
		 * 	左递归以left为起点,mid为终点,右递归以mid + 1位起点,right为终点,当递归结束时
		 * 	表示该数组已经分割到不可分割了,此时就可以将数据进行排序合并了,调用合并的方法
		 * 	当整个方法执行结束后整个数组排序就完成了
		 */
		if (left < right){
			int mid = (left + right) / 2;
			//左递归
			sortMerge(arr,left,mid,temp);
			//右递归
			sortMerge(arr,mid + 1,right,temp);
			//合并
			merge(arr,left,mid,right,temp);
		}
	}
	
	//基数排序,使用8百万数据进行排序,耗时1.2s左右
	/*此方式在排序时可以说非常快,但也有明显的缺点,在开始时就定义了10个数组
	 *当数据量特别大时,达到8千万时,对内存的消耗是巨大的
	 *80000000 * 10 * 4
	 */
	public static void sortJiShu(int[] arr){
		//首先获取数组中的最大数
		int max = 0;
		for (int i = 0; i < arr.length; i++) {
			if (max < arr[i]) {
				max = arr[i];
			}
		}
		//获取此最大数的位数
		int wei = (max+"").length();
		/*
		 * 定义10个桶,这里使用二维数组定义,其中第一层是固定10代表
		 * 每位上的数字都是0-9,第二层是放置数据的,在这里需要注意的是
		 * 可能所有的数据都放在一个桶里,所以第二层的长度是arr.length
		 */
		int[][] tong = new int[10][arr.length];
		/*
		 * num是用于记录每个桶里有几个数据,当放入一个数据时将其对应桶的数字++
		 * 它也是10个数字,对应10个桶,
		 */
		int[] num = new int[10];
		
		int index;
		//因为是到最大位数时就结束了,所以是从0开始循环到wei结束k < wei
		int k = 0;
		while (k < wei){
			/*
			 * 计算每个位上的数字,公式为 number / 10^k % 10;
			 * 由于k是每次循环就确定了,所以在这里计算10^k次方值
			 */
			int nn = (int)Math.pow(10, k);
			/*
			 * 循环数组中的每个数据
			 */
			for (int i = 0 ; i < arr.length ; i ++){
				//获取对应循环位上的数字,从个位开始
				int n = arr[i] / nn % 10;
				//将此值放入对应的桶中
				tong[n][num[n]] = arr[i];
				/*
				 * num[n]记录了该桶中有几个数据,同样也记录着该数据在桶中的位置
				 * 当放入一个数据时需要进行++操作
				 */
				num[n]++;
			}
			//index是指向原数组的指针,在上面已经将数据按照需要放到了每个桶中,这里
			//需要将桶中的数据再按照桶的顺序取出放入原数组中
			index = 0;
			//开始循环每个桶
			for (int a = 0 ; a < tong.length ; a++){
				/*
				 * 在这里并不是每个桶都有数据,可能某个桶里根本没有数据
				 * 而桶里是否有数据正好记录在num数组中,因为在上面每向桶里
				 * 放入一个数据时,其对应的num数组元素就会进行++,所以这里
				 * 判断num[a] > 0时表示该桶中存有数据,而存的数据个数刚好
				 * 是num[a]个,因为它记录着该桶中的数据个数
				 */
				if (num[a] > 0){
					//循环该桶的数据
					for (int l = 0 ; l < num[a] ; l++){
						//将每个桶中的数据依次放入arr数组中
						arr[index++] = tong[a][l];
					}
				}
				//当结束后需要将记录每个桶数据的信息置为0,用以下次的使用,
				//这里不重新赋为0的话会影响下次桶中的有效数据量
				num[a] = 0;
			}
			//步长
			k++;
		}
	}
	
	
	//堆排序
	public static void sortDuiChu(int[] arr){
		int mid = arr.length / 2 - 1;
		int last = arr.length - 1;
		int pre = 0;
		int index = 0;
		int temp = 0;
		while (last > 0){
			while (mid >= 0) {
				index = mid * 2 + 1;
				if(arr[index] > arr[mid]){
					temp = arr[index];
					arr[index] = arr[mid];
					arr[mid] = temp;
				}
				if(arr[index + 1] > arr[mid]){
					temp = arr[index + 1];
					arr[index + 1] = arr[mid];
					arr[mid] = temp;
				}
				mid --;
			}
			pre = arr[0];
			arr[0] = arr[last];
			arr[last] = pre;
			last--;
			mid = 0;
		}
	}
	
	//堆排序
	public static void sortDui(int[] arr){
		int mid = arr.length / 2 - 1;
		int last = arr.length - 1;
		int pre = 0;
		int index = 0;
		int temp = 0;
		int index1 = 0;
		while (last > 0){
			while (mid >= 0) {
				temp = arr[mid];
				index1 = mid;
				index = mid * 2 + 1;
				while (index <= last) {
					if (index + 1 <= last && arr[index + 1] > arr[index]) {
						index++;
					}
					if (arr[index] > temp) {
						arr[index1] = arr[index];
						index1 = index;
					}else{
						break;
					}
					index = index * 2 + 1;
				}
				arr[index1] = temp;
				mid --;
			}
			pre = arr[0];
			arr[0] = arr[last];
			arr[last] = pre;
			last--;
			mid = 0;
		}
	}
	
	/*
	 * 堆排序主方法:
	 * 在主方法中:由于节点转大顶堆的方式已经订好,把数组转成大顶堆后
	 * 将头节点arr[0]与尾节点进行互换即可,在下一次的大顶堆排列时,不再
	 * 对最后一个值进行排列
	 */
	public static void sortDuiMain(int[] arr){
		//首先:将整个树从最后一个子树开始按照大顶堆的方式进行交换排列
		for (int a = arr.length / 2 - 1; a >= 0; a--) {
			sortDui1(arr, a, arr.length);
		}
		/*
		 * 当进过首次大顶堆排列后,整个树的每个节点都是满足大顶堆要求的
		 * 然后将头节点与尾节点进行交换,交换后由于仅头节点不满足大顶堆的要求
		 * 所以这里仅对头节点进行大顶堆的排列,其他节点依次向上移动,将头节点的值
		 * 放置在对应位置即可,而不用在像上面一样还是从最后一个子树开始进行大顶堆的
		 * 排列了
		 */
		//这里的循环是每次减少一个节点
		for (int s = arr.length - 1 ; s > 0; s --) {
			//将头节点与尾节点进行交换
			int temp = arr[0];
			arr[0] = arr[s];
			arr[s] = temp;
			//对头节点进行大顶堆的排列
			sortDui1(arr, 0, s);
		}
	}
	
	//堆排序:数组转大顶堆方法
	/*
	 * 首先写一个方法:
	 * 		针对某个节点的子树对其完成该子树及其下面子树转换为大顶堆的形式
	 */
	public static void sortDui1(int[] arr,int i,int length){
		//首先我们把该节点的值取出,进行记录
		int temp = arr[i];
		/*
		 * 遍历:这里的遍历是即遍历该子树,也遍历该子树下面的子树
		 * 这里的思路分为两条线说明
		 * 	1.当节点1的子树下面没有子树时:
		 * 		这时仅获取出节点1的左右节点最大值,拿这个最大值跟节点1的值比较,
		 * 	节点1的值小时进行交换,大时不交换,由于没有它下面再没有子树所以到这里
		 * 	结束
		 * 	2.当节点1的子树下面还有子树时:
		 * 		这种情况有一个前提条件,就是在此之前节点1下面的子树已经进过了大顶堆的排列
		 * 	满足大顶堆,这时由于节点1的值可能是一个较小值,先判断节点1的子树的最大值,将最大值
		 * 	向根节点移动,移动后将一个指针指向需要移动的节点上,在获取该节点下的子节点,获取出
		 * 	最大值,再将最大值向根节点移动,直到不满足时,节点1的值就放在了指针指向的节点位置
		 * 	它是在其子树已经是大顶堆的基础上才可进行的
		 */
		for(int k = i * 2 + 1 ; k < length ; k = k * 2 + 1){
			//k指向的是传入节点的左子节点,k需要小于数组长度,步长是子节点下的左子节点
			//
			/*
			 * 判断左子节点和右子节点的最大值,将k指向最大值的索引,这里k++的原因还有一个
			 * 就是当右子节点大时,在下一次循环时,需要验证右子节点下的节点
			 */
			if(k + 1 < length && arr[k] < arr[k + 1]){
				k++;
			}
			/*
			 * 当获取的子节点最大值 > 传入的节点的值时,将这个子节点的最大值向上移动,挪动到
			 * 主节点的位置上,而同时i指向k,i就相当于一个指针了,指在了当前最大值的子节点索引
			 * ,在下一次进行循环时,会将找到的较大值再次放在原本arr[k]的位置上,因为原本的arr[k]
			 * 值已经向上移动了,所以下一次直接覆盖即可,如果不满足arr[k] > temp,那么就表示temp
			 * 的值就是该子树的根节点,将temp的值放在arr[i]的位置上即可
			 */
			if(arr[k] > temp){
				arr[i] = arr[k];
				i = k;
			}else{
				break;
			}
		}
		/*
		 * 跳出循环时表示,在上面的arr[k] > temp的判断中失败,也就是传入的节点值temp,在此时
		 * 比某个子树下的两个节点值都大,那么传入的节点值就可以放置在该位置上
		 */
		arr[i] = temp;
	}
}
